package com.cat.dataStructure03;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-discards-to-balance-inventory/description/
 * @create 2025/11/11 12:33
 * @since JDK17
 */

public class Solution44 {
    public int minArrivalsToDiscard(int[] arrivals, int w, int m) {
        int ans = 0, n = arrivals.length;
        Map<Integer, Integer> map = new HashMap<>();
        boolean[] h = new boolean[n];
        for (int l = 0, r = 0; r < n; l++) { //
            while (r < l + w && r < n) { //
                int cnt = map.getOrDefault(arrivals[r], 0) + 1;
                if (cnt > m) { // 必须抛弃
                    h[r] = true;
                    ans++;
                } else {
                    map.put(arrivals[r], cnt);
                }
                r++;
            }
            if (!h[l]) {
                map.merge(arrivals[l], -1, Integer::sum);
            }
        }

        return ans;
    }
}
